package main;

import java.util.*;

/**
 * 给定一个字符串，找出不含有重复字符的最长子串的长度。
 * <p>
 * 示例 1:
 * 输入: "abcabcbb"
 * 输出: 3
 * 解释: 无重复字符的最长子串是 "abc"，其长度为 3。
 * 示例 2:
 * 输入: "bbbbb"
 * 输出: 1
 * 解释: 无重复字符的最长子串是 "b"，其长度为 1。
 * 示例 3:
 * 输入: "pwwkew"
 * 输出: 3
 * 解释: 无重复字符的最长子串是 "wke"，其长度为 3。
 * 请注意，答案必须是一个子串，"pwke" 是一个子序列 而不是子串。
 */
@SuppressWarnings("unchecked")
public class LeetCode3 {
    public int lengthOfLongestSubstring(String s) {
        char[] arr_s = s.toCharArray();  // 转换成数组,不转也行
        ArrayList<Character> counted = new ArrayList(); // 存放已经记录的字串
        int max = arr_s.length > 0 ? 1 : 0;     // 记录当前的最大值,如果传入的串为空则为0,否则最小为1
        for (int i = 0; i < arr_s.length; i++) {
            counted.add(arr_s[i]);  // 添加当前位置进入记录
            int j = i + 1;      // 从下一个位置开始
            for (; j < arr_s.length; j++) {
                if (counted.contains(arr_s[j])) {  // 如果包含,则请空记录,并跳出该循环
                    counted.clear();
                    break;
                } else { // 不存在则添加当前字符,并更新最大值
                    counted.add(arr_s[j]);
                    max = counted.size() > max ? counted.size() : max;
                }
            }
            if (j == (arr_s.length - 1)) {  //若字串持续到串结束,跳出外循环
                break;
            }
        }
        return max;
    }

    public int lengthOfLongestSubstring1(String s) {  // 官方解法一:暴力破解
        int n = s.length();
        int ans = 0;
        for (int i = 0; i < n; i++)
            for (int j = i + 1; j <= n; j++)
                if (allUnique(s, i, j)) ans = Math.max(ans, j - i);
        return ans;
    }


    public boolean allUnique(String s, int start, int end) {
        Set<Character> set = new HashSet<Character>();
        for (int i = start; i < end; i++) {
            Character ch = s.charAt(i);
            if (set.contains(ch)) return false;
            set.add(ch);
        }
        return true;
    }

    /**
     * 官方解法二:滑动窗口
     * 使用HashSet存放已经校验无重复的窗口
     * 当检测到重复时向某个方向滑动
     */
    public int lengthOfLongestSubstring2(String s) {
        int n = s.length();
        Set<Character> set = new HashSet<Character>();
        int ans = 0, i = 0, j = 0;
        while (i < n && j < n) {
            // try to extend the range [i, j]
            if (!set.contains(s.charAt(j))) {
                set.add(s.charAt(j++));
                ans = Math.max(ans, j - i);
            } else {
                set.remove(s.charAt(i++));
            }
        }
        return ans;
    }

    /**
     * 官方解法三:优化的滑动窗口
     * 如果 s[j] 在 [i,j) 范围内有与j′
     * 重复的字符，我们不需要逐渐增加 i。我们可以直接跳过[i，j′]
     * 范围内的所有元素，并将 i变为j′+1。
     */
    public int lengthOfLongestSubstring3(String s) {
        int n = s.length(), ans = 0;
        Map<Character, Integer> map = new HashMap<Character, Integer>(); // current index of character
        // try to extend the range [i, j]
        for (int j = 0, i = 0; j < n; j++) {
            if (map.containsKey(s.charAt(j))) {
                i = Math.max(map.get(s.charAt(j)), i);
            }
            ans = Math.max(ans, j - i + 1);
            map.put(s.charAt(j), j + 1);
        }
        return ans;
    }


    public static void main(String[] args) {
        LeetCode3 leetCode3 = new LeetCode3();
        System.out.println(leetCode3.lengthOfLongestSubstring("abcabcbb"));
        System.out.println(leetCode3.lengthOfLongestSubstring("bbbbb"));
        System.out.println(leetCode3.lengthOfLongestSubstring("pwwkew"));
        System.out.println(leetCode3.lengthOfLongestSubstring(""));
    }
}
